package com.huangyi;

public class Main {
    public static void main(String[] args) {
        //合并两个有序链表
        /**
         * Definition for singly-linked list.
         * public class ListNode {
         *     int val;
         *     ListNode next;
         *     ListNode() {}
         *     ListNode(int val) { this.val = val; }
         *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
         * }
         */
        class Solution {

            // 递归版：按头取最小，递推到子问题
            public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
                return merge(list1, list2);
            }

            private ListNode merge(ListNode list1, ListNode list2) {
                // 1) 处理递归边界：有一条为空，答案就是另一条
                if (list1 == null) return list2;
                if (list2 == null) return list1;

                // 2) 选较小（含等于）者作为当前头结点，保证 stability
                if (list1.val <= list2.val) {
                    // 3) 把“剩余部分的合并结果”接到被选节点后面
                    list1.next = merge(list1.next, list2);
                    return list1;
                } else {
                    list2.next = merge(list1, list2.next);
                    return list2;
                }
            }
        }


        //反转链表
        class Solution2 {
            public ListNode reverseList(ListNode head) {
                if(head == null) return null;
                ListNode result = revers(head);
                return result;
            }

            public ListNode revers(ListNode head){
                // 边界情况, 递归到最后一个时返回, 返回的第一层就是倒数第二个节点
                if(head.next == null) return head;

                // 返回的第一层就是倒数第二个节点
                ListNode prev = revers(head.next);
                head.next.next = head;
                head.next = null;;
                // 尾指向倒数第二个, 倒数第二个指向尾曾经指向的 next 保证不断尾。

                return prev;
            }

        }
    }
}